﻿using System;
using System.Collections.Generic;
using Pagination.RangeCollector;

namespace Pagination.Storage
{
    public class RBTreeStorage : IStorage
    {
        private static uint REDMASK = 0x80000000;
        private readonly IRangeCollector collector;
        private Node Root;

        private int _leftCount;


        private Stack<Tuple<Node, bool>> stack = new Stack<Tuple<Node, bool>>();

        public RBTreeStorage(IRangeCollector collector)
        {
            this.collector = collector;
            Root = null;
        }

        #region IStorage Members

        public void Range(int left, int right)
        {
            stack.Clear();
            var aLength = right - left + 1;
            var i = 0;
            GetNodeByIndex(left - 1, stack);
            while (stack.Count != 0)
            {
                if (i == aLength)
                    break;
                var node = stack.Pop();
                collector.Append(node.Item1.Item);
                i++;
                if (node.Item1.Right != null)
                {
                    int end = stack.Count;
                    stack.Push(new Tuple<Node, bool>(node.Item1.Right, false));
                    while (i < aLength && stack.Count != end)
                    {
                        var llnode = stack.Pop();
                        if (llnode.Item2)
                        {
                            collector.Append(llnode.Item1.Item);
                            i++;
                            continue;
                        }
                        int c = i + (llnode.Item1.Left == null ? 0 : llnode.Item1.Left.Count);
                        if (llnode.Item1.Right != null && c < aLength)
                            stack.Push(new Tuple<Node, bool>(llnode.Item1.Right, false));
                        if (llnode.Item1.Left != null)
                        {
                            stack.Push(new Tuple<Node, bool>(llnode.Item1, true));
                            stack.Push(new Tuple<Node, bool>(stack.Peek().Item1.Left, false));
                        }
                        else
                        {
                            collector.Append(llnode.Item1.Item);
                            i++;
                        }
                    }
                }
            }
            collector.End();
        }

        public void Add(int item)
        {
            var node = Root;
            Node parent = null, gparent = null, ggparent = null;
            bool wentLeft = false, wentRight = false;
            while (node != null)
            {
                if (node.Left != null && node.Left.IsRed && node.Right != null && node.Right.IsRed)
                {
                    node = InsertSplit(ggparent, gparent, parent, node);
                }
                ggparent = gparent;
                gparent = parent;
                parent = node;
                node.Count++;
                if (item < node.Item)
                {
                    node = node.Left;
                    wentLeft = true;
                    wentRight = false;
                }
                else
                {
                    node = node.Right;
                    wentRight = true;
                    wentLeft = false;
                }
            }
            node = new Node(item, 1);
            if (wentLeft)
                parent.Left = node;
            else if (wentRight)
                parent.Right = node;
            else
                Root = node;
            InsertSplit(ggparent, gparent, parent, node);
        }

        #endregion

        private void GetNodeByIndex(int index, Stack<Tuple<Node, bool>> stack)
        {
            var current = Root;
            for (;;)
            {
                _leftCount = current.Left != null ? current.Left.Count : 0;

                if (_leftCount > index)
                {
                    stack.Push(new Tuple<Node, bool>(current, false));
                    current = current.Left;
                }
                else if (_leftCount == index)
                {
                    stack.Push(new Tuple<Node, bool>(current, false));
                    return;
                }
                else
                {
                    index -= _leftCount + 1;
                    current = current.Right;
                }
            }
        }

        private Node InsertSplit(Node ggparent, Node gparent, Node parent, Node node)
        {
            if (node != Root)
                node.IsRed = true;
            if (node.Left != null)
                node.Left.IsRed = false;
            if (node.Right != null)
                node.Right.IsRed = false;

            if (parent != null && parent.IsRed)
            {
                if ((gparent.Left == parent) != (parent.Left == node))
                {
                    Rotate(gparent, parent, node);
                    parent = node;
                }
                gparent.IsRed = true;
                Rotate(ggparent, gparent, parent);
                parent.IsRed = false;
                return parent;
            }
            return node;
        }

        private void Rotate(Node node, Node child, Node gchild)
        {
            if (gchild == child.Left)
            {
                child.Left = gchild.Right;
                gchild.Right = child;
            }
            else
            {
                child.Right = gchild.Left;
                gchild.Left = child;
            }
            child.Count = (child.Left != null ? child.Left.Count : 0) + (child.Right != null ? child.Right.Count : 0) +
                          1;
            gchild.Count = (gchild.Left != null ? gchild.Left.Count : 0) +
                           (gchild.Right != null ? gchild.Right.Count : 0) + 1;
            if (node == null)
            {
                Root = gchild;
            }
            else if (child == node.Left)
            {
                node.Left = gchild;
            }
            else
            {
                node.Right = gchild;
            }
        }

        #region Nested type: Node

        public class Node
        {
            public int Item;
            public Node Left;
            public Node Right;

            private uint _count;

            public Node(int item, int i)
            {
                Item = item;
                Count = i;
            }

            public bool IsRed
            {
                get { return (_count & REDMASK) != 0; }
                set
                {
                    if (value)
                        _count |= REDMASK;
                    else
                        _count &= ~REDMASK;
                }
            }

            public int Count
            {
                get { return (int) (_count & ~REDMASK); }
                set { _count = (_count & REDMASK) | (uint) value; }
            }

            public new string ToString()
            {
                return Item + " (" + (Left == null ? "null" : Left.Item.ToString()) + "," +
                       (Right == null ? "null" : Right.Item.ToString()) + ")";
            }
        }

        #endregion
    }
}